Shareware Grab Bag/Shareware Grab Bag.iso/090/aztcmtsk.arc/AZTASK.DOC

Text File | 1986-03-24 | 23KB | 539 lines

           CONCURRENCY AND AZTEC C (8080/Z80)
         Copyright 1986 David E. Cortesi

     In DDJ #113 (March 1986), Ernest Bergmann describes in
"Concurrency and Turbo Pascal" a simple method of building a
multitasking program under Borland's Turbo Pascal.
     Turbo Pascal gave Bergmann easy access to the system's stack
pointer, which made his work easy.  I wondered if the same thing
could be done in C, specifically in the Manx AZTEC C for the 8080
which is all I had use of.  The answer is, yes it could, and I
did it.  This is a documentation file for it.

----- Simple multitasking

     What Bergmann demonstrates is the use of independent,
cooperating tasks, dispatched under a nonpreemptive, voluntary,
round-robin discipline.  Taking those words one at a time:
     Independent tasks -- each functional unit of the program
executes independently and asynchronously from all other units.
This is a powerful mental tool for program design; it enforces
clean, watertight separation of jobs to modules.  However, the
asynchonicity implies that there will have to be some mechanism
by which tasks can get in touch with each other and synchronize
their efforts.    Bergmann demonstrates a good mechanism, the FIFO
queue.
     Cooperating tasks -- the program units have to be written
with the knowledge that they will be used together, and they have
to follow certain rules for the program as a whole to work.
Contrast this with a general multitasking operating system like
UNIX, under which you can run any mix of programs simultaneously
and they don't have to be aware of each other.
     Nonpreemptive discipline -- in the general operating system,
the system itself can seize control from the task currently
running, and give the CPU to another task.  That's a preemptive
scheduling discipline, under which the scheduler can preempt one
task in favor of another (on an interrupt, for example).
Bergmann demonstrates a nonpreemptive discipline, in which a task
gives up control only when it is ready to.
     Voluntary discipline -- each task gives up control at
specified points in its code, by calling a procedure named
"defer" (in order to "defer" to its fellow tasks).  If a task
runs a long time without defer-ing, its sibling tasks will be
starved for CPU time.  If a task gets hung up waiting for input,
the whole program hangs with it.
     Round-robin scheduling -- the tasks are kept in a list which
is never reordered, and calling defer always passes control to
the next task in the list.  Contrast this to a scheduling system
that has some policy for reordering the list, or some more
complicated rule for scanning it than merely going around and
around.  Such schemes are "prioritized" disciplines.
     In Bergmann's demonstration, every task always executes on
its turn.  It is possible to enhance round-robin scheduling with
a method of "blocking" a task, so that it is skipped on its turn.

     In its simplicity, this style of multitasking has a strong
resemblance to design with coroutines.    A call to defer is like a
coroutine linkage, except that it doesn't state which coroutine
is to be called -- the round-robin scheduling list determines
that, and it's external to the code of a task.
     Despite its simplicity, the scheme is a powerful design
tool.  For one example, I think that the natural organization for
a "modem" program is as a family of cooperating tasks linked by
fifo queues.  One task minds the modem input, one the keyboard,
one the screen, one the modem output, one the printer -- and a
central task acts as a switchboard operator to route data among
them.  Simulations also fall nicely into families of tasks.  Even
if its implementation was too slow or otherwise limited, Bergmann
showed us a great tool for learning and teaching these concepts.
I tried to make the C version as useful.

----- Files for Aztec C Tasking

     My implementation of Bergmann's concept is strictly for
Aztec C for the 8080/Z80 (A copyright product of Manx Software).
It depends on 8-bit hardware in that it assumes a pointer and an
unsigned integer are compatible, and it depends on the storage
and stack allocation methods used by the Aztec compiler.
Figuring that tasking in any other compiler would require
similar, but unique, fudges, I made no attempt to flag these
dependencies.
     This compiler doesn't support the "void" storage class, UNIX
standard storage allocation functions, or the stronger
type-checking of newer C compilers.  I've tried to indicate in
the code where these things should be used if they are available.

     The tasking implementation is in these files:

    AZTASK.DOC -- this file
    AZTASK.TSC -- the source of TASKING.C, the code
    AZTASK.TSH -- the source of TASKING.H, the interface
    AZTASK.CRT -- the source of TROOT.C, modified CROOT

TASKING.C contains the code of the functions that implement
tasking and queues.  These functions are documented below.  It
also contains a revision of the alloc() function, since the
original didn't work with tasking.
     TASKING.H is an include file that contains definitions of
three data structures, Task, Queue, and Event (initial caps on
each structure name), and extern declarations of all the
functions in TASKING.C.
     TROOT.C is a modification of the original CROOT.C.  For
those unused to C practice, the function croot() is the real
beginning of any C program.  It has the code to parse the command
line into tokens, set up "argc" and "argv," and call the function
main().  Its source is normally given out with any compiler so
that you may alter the way the environment is set up for a
program.
     This CROOT has been modified in several ways: with
improvements (suggested by Allen Holub) in the way it handles the
CP/M command line and with a fix for the poor performance of
redirected stdout files.  And here it has been altered so that,
instead of CALLING your main() function, it makes a TASK of it.
The main() function is initially the only task in the round-robin
list, and croot() kicks it off by calling defer().

----- Linking and Debugging

     You must have Aztec C for the 8080/Z80 in order to use these
files.    Download them to their proper names as indicated above.
Compile and assemble TROOT.C and TASKING.C, producing TROOT.O and
TASKING.O.
     Then, when you have a tasking program ready (the sample that
follows, for instance), link it with a command like

    ln -t myprog.o troot.o tasking.o libc.lib

By naming TROOT.O and TASKING.O before the standard library, you
ensure that the modified croot(), alloc(), and the tasking and
queueing functions are linked.    The -t option creates a symbol
table.    I find that if it is forced to uppercase --

    pip myprog.sym=myprog.sym[u]

-- it can be used with the SID debugger, which is VERY helpful
for tasking problems:

    sid myprog.com myprog.sym

When debugging an Aztec C program with SID, keep in mind that
every compiled function commences with a call to a stack setup
routine followed by an inline parameter:

    CALL START
    DW   size-of-locals-often-0x0000
    first instruction of function

Set pass points and break points 5 bytes after the name of a
function to stop on its first instruction.  Remember also that
the compiler appends an underbar to each function name less than
8 bytes long.  Here's how to get to the start of the main()
function, then set a pass point in defer().

    sid myprog.com myprog.sym
    -i [tokens for command line here]
    -g,.main_+5
    (stop display at start of main)
    -p,.defer_+5

The following example program demonstrates the simplest use of
queues and tasks.  (See beyond it for the documentation of the
called functions.)

#include "stdio.h"    /* for printf */
#include "tasking.h"    /* interface to tasking and queues */
#define NUM 5        /* test iterations */

int rdrfun();          /* forward declaration of task functions,*/
int wrtfun();          /* so they can be named to maketask() */

main(argc,argv) int argc; char *argv[];
{
struct Task *rdr, *wrt;
struct Queue *bfr;

    bfr = qmake(NUM); /* experiment with NUM-1, and 1 */

    /* experiment with reversing this order */
    wrt = maketask(wrtfun,256,1,bfr);
    rdr = maketask(rdrfun,256,1,bfr);

    printf("rdr Task  %04x\n",rdr);
    printf("wrt Task  %04x\n",wrt);
    printf("main task ending\n");
    endtask();    /* explicit endtask call */
}

rdrfun(bfr) struct Queue *bfr;
{
int j;
    printf("reader started\n");
    do
    {
        j = qget(bfr);
        printf("reading %d\n",j);
    } while (j<NUM);
    printf("reader function exiting\n");
    return; /* endtask is automatic */
}

wrtfun(bfr) struct Queue *bfr;
{
int j;
    printf("writer started\n");
    for(j = 0; j<=NUM ; ++j)
    {
        printf("writing %d, ",j);
        qput(bfr,j);
        printf("..and deferring\n");
    /* experiment with removing this defer and with */
    /* making it conditional on odd(j), etc. */
        defer();
    }
    printf("writer function exiting\n");
}

----- The Tasking functions

A "task" consists of a unit of code plus the present state of its
variables.  The code of a task is specifically a single function
and the functions it calls.  Its execution state is maintained in
a call-stack as usual, but the stack will be more limited in size
than usual in a C program.  Tasks are created by maketask() --

    struct Task *maketask(func,size,narg [,parms...])
        int (*func)(), size, narg;

The first argument is the address of the function that will
execute as this task.  It will be entered at its first statement
the next time defer() is called.

The second argument is the number of words that "func" needs in
its stack.  This depends on the number of local variables it (and
the functions it calls) uses.  THERE ARE NO STACK-OVERFLOW
CHECKS!  512 words, a kilobyte, is probably sufficient, but by
all means use more if you like.

The third argument is the count of parameters to be passed to
"func," while the parameters themselves follow.  The example
program above shows making two tasks each with one parameter.
For another example, croot() kicks off the function main() with
the following statements:

    extern int main();
    maketask(&main,256,2,argc,argv);
    defer();

Any task may create other tasks, and any function may be started
off as a task as many times as you like.  Each new task is
inserted into the round-robin list immediately following the task
that creates it, and thus immediately ahead of its siblings.
This order can affect the behavior of a program (experiment with
the example program to see).  For instance, if two tasks are
taking items from the same queue, the task that comes first in
the list can starve the one that comes second.

     Once started, a task will end and be removed from the list
in one of three ways.  It may end itself with a call to --

    void endtask()

from which there is no return.    Or it may simply return, because
the address of endtask() is pushed onto its initial stack by
maketask().  Or its creator (or any other task that has its
address) may kill it with --

    void killtask(adt)
        struct Task *adt;

All of these have the same effect: the task is marked and the
next time defer() reaches it, it is dropped from the dispatch
list.  When no live tasks remain, the program ends and returns to
CP/M.

     Each task must voluntarily give up control, and do it often.
This can be done with a call to --

    void defer()

The defer() function saves the stack pointer of the current task
and then scans along the round-robin list to find the next task
that is ready to run.  (Tasks can be sleeping or blocked, see
below.)  If NO task is ready to run, the program is in deadlock,
and defer() prints a message on stderr and ends the program.  If
it finds a dead task, it removes it from the list.
     Usually it will find a task to run.  It makes that task the
current task, loads its saved stack pointer into the hardware SP,
and returns to it.  In the case of a new task, it's as if there
was a call to defer() immediately before the actual first
statement of the task function.  In all other cases, there was an
actual call to defer() from which control now returns.    Think of
"defer" as a subroutine that contains the code of every other
task; you call it so they can run, then it returns and you run
again.
     The qget() function (below) also contains a call to defer().
A call to one of these functions MUST appear in the central loop
of every task, or the program will bog down.  If tasks don't
voluntarily give up control very frequently (every tenth of a
second or so) the illusion of simultaneous execution breaks down.
If any task lets itself get hung up on input from the keyboard,
or any other operation with an unpredictable delay time, all
other tasks will be hung up while it is hung up.

     In some cases it may be useful for a task to get the address
of its own Task structure.  This is returned by --

    struct Task *myTask()

     In some applications there may be a need to put a task to
sleep.    This can be done with --

    void tsleep(adt) struct Task *adt

which marks the task *adt as sleeping.    Then defer() will simply
skip over it until it has been awakened with --

    void twaken(adt) struct Task *adt

One possible use of these functions is with a timer task.  A task
could pass its own Task to a task that managed a timer, along
with a delay value.  The timer task could then tsleep() its
client, wait until the delay had elapsed, and twaken() it.

     The status of a task can be checked with --

    int tactive(adt) struct Task *adt

which returns 1 if the named task is active (would be able to run
the next time defer() gets to it) and 0 otherwise.  Additional
information can be gotten from --

    unsigned tinact(adt) struct Task *adt

which returns 0 if the task is active, 0x0001 if it has been put
to sleep by tsleep(), 0xffff if it has been killed or ended, and
some other nonzero value if it is blocked on a get or put to a
queue.    Quick quiz: what value will the expression tinact(myTask)
always have and why?

----- The FIFO-Queue Functions

A set of cooperating tasks usually needs some way of
communicating data from one task to another.  Since they may run
at different speeds, they usually need some way of buffering data
between them so that the sender of data can temporarily produce
it faster than the consumer consumes it.  These needs are nicely
met by the FIFO queue.    I have included with the tasking
functions a set of functions for managing fifo queues of unsigned
words.
     Although a Queue structure is defined in TASKING.H, a Queue
cannot be declared statically; it must be allocated dynamically
by a call on --

    struct Queue *qmake(num) int num

to create a fifo queue that can contain at most "num" words.  The
number of words that are needed in a queue is the subject of an
interesting branch of mathematics, queueing theory, and
simulations of problems in queueing theory can be built with this
or Bergmann's tasking system.

When a task wants to put an item into a queue, it does so with --

    void qput(adq,val) struct Queue *adq; unsigned val

The value "val" is appended to the queue as its newest item.  If
the queue is presently full, the active task is said to be
"blocked."  It is marked and defer() is called; it will not run
again until some other task does a get from this queue, at which
time the qput will complete and the task will again be active.
     If another task had been blocked on a get from this queue,
it is unblocked and will retrieve "val" the next time defer()
runs it.  If more than one task had been blocked getting from
this queue, all will be unblocked and the next one in round-robin
sequence will succeed in retrieving "val" (the rest will probably
be blocked again).

When a task wants to get an item from a queue, it does it with --

    unsigned qget(adq) struct Queue *adq

The first thing qget() does is call defer().  This is for
simplicity, because typical "consumer" tasks will contain a
qget() call in their central loops and won't have to have a
defer() as well.  It's also for efficiency, since a defer()
before a get increases the likelihood that the supplying task
will have put a value in the queue, thus decreasing the need for
blocking the active task.  (The qput() function doesn't do a
defer; writing tasks have to defer explicitly.)
     After the defer(), the oldest item in the queue is
retrieved.  If the queue is in fact empty, the task is blocked,
that is, marked inactive and defer() is called (again).  The task
will not run again until some other task puts an item into the
queue; then the qget will complete and return a value.
     If a task has been blocked waiting to put an item in this
queue, it is unblocked and will be able to finish its qput()
call.  If more than one task has been blocked on put, all will be
unblocked and the next in round-robin sequence will complete its
put (the rest will probably be blocked again).

All this blocking can be avoided by testing the queue with --

    int qempty(adq) struct Queue *adq

which returns 1 if the queue is empty (qget() would block),
otherwise 0; or with --

    int qnotmt(adq) struct Queue *adq

the logical inverse of qempty(); or with --

    int qfullQ(adq) struct Queue *adq

which returns 1 if the queue is full (qput() would block),
otherwise 0; or with --

    int qnotfull(adq) struct Queue *adq

which is the logical inverse.
     For example, the task that manages the input side of a modem
might want to put each incoming byte into a fifo for the printer
task, provided that the operator has turned on print logging.
However, if the printer is out of paper the printer fifo might
fill up, and the modem-input task mustn't get blocked or it will
lose input data.  Here's how such a task might look:

    do
    {
        defer();
        get-modem-status-bits;
    } while (modem-input-not-ready);
    c = get-modem-data-input-byte;
    if (terminalmode)
    {
        qput(screenfifo,c);
        if (disklogging)
            qput(diskfifo,c);
        if (printlogging)
            if (qnotfull(printfifo))
                qput(printfifo,c);
    }
    else qput(xmodemfifo,c);

The task assumes the screen and disk-log tasks can consume data
at least as fast the modem can produce it, but the printer fifo
might fill up and stay full for unpredictable lengths of time.

----- The Synchronizing Functions

     Now, often a program will want to pass objects larger than
an unsigned word.  This can be done, of course, by passing
pointers to objects through the queues, but that brings up
problems of synchronization.  Suppose that task A puts the
address of a block of data in a queue for task B to consume.
When can task A safely re-use that block of data?  Answer: it
cannot know.  There's no way of telling when task B will start,
much less finish, working on that block.  The only safe thing to
do is to wait until task B TELLS task A it is finished.
     This is the central problem of synchronization: how can task
B tell task A it's done?  Here are some possibilities.  First,
task A could pass its own Task along with the data, and tsleep()
itself after putting the item in B's fifo.  Task B would be
expected to twaken() task A when the work was done.  This
precludes task A doing anything useful in the meantime.
     Second, the tasks can use an Event as a synchronizer.  An
Event is simply a fifo queue that has room for only one word.
Task A sends the block of data to task B in a different queue,
then attempts to get an item from the Event they share (or A
might have passed the address of the Event along with the data).
Since a qget from an empty queue blocks a task, this is the
equivalent of A's sleeping itself.  When task B has finished,
it will qput an arbitrary value (or a useful return code) into
the Event, so waking up task A.  As with the tsleep() solution,
this precludes task A doing anything useful while task B is
working, but that's inevitable anyway, if their work centers on
sharing a single object (buffer, block, whatever).
     Third, the tasks could agree on the use of a global, static
variable as a synchronizing flag.  Task A would put a 1 in it,
send the block of data, and then spin in a loop:

    do {defer();} while(synchro);

When task B was done, it would set 0 in the variable.  This allows
task A to do other things besides defer() while it is waiting, but
it adds needless overhead in the fruitless dispatches of task A.
     If their resources are larger, they can adopt a fourth
solution, the "full-duplex" method.  Here they share a pair of
fifo queues.  One, from B to A, contains the addresses of all the
free objects (buffers, whatever), while the other from A to B
contains the addresses of all the ones that A has filled up for
B to empty.  The objects move between the tasks like cars on a
tramline.
     An Event may act to control access to a single resource that
may be used by only one task at a time.  The resource is
represented by a word in the Event.  A task acquires the
resource by getting a word from the Event, and releases it by
putting the word back.    However, in this implementation, tasks
that are waiting for Events (blocked on empty queues) are not
queued up in the order they accessed the queue.  When the
resource is put back in the Event, all tasks that are waiting for
it are unblocked at once.  The one that gets it will be the one
that comes next in round-robin order after the task that released
the resource.  This results in an equitable sharing of a
resource (it will be handed around the the dispatch list like
the gravy boat at the supper table) but not a "fair" one in the
usual sense since the task that receives a resource will not
necessarily be the one that has waited the longest for it.

An Event is created by the special function --

    struct Event *evmake();

which makes a single package Event of 7 words.    A call of
qmake(1) will make a functionally equivalent Event, but a queue's
array of fifo data is allocated separately from its Queue
structure.
     You wait on an event with evwait(), which is merely --

    #define evwait(E) qget((E))

and post one on which another task is waiting with evpost() --

    #define evpost(E) qput((E),1)

although an explicit qput with an informative return code value
will often be better.  An event can be tested without waiting on
it with evwait() --

    #define posted(E) qnotmt((E))

It would be possible to build much more elaborate synchronizing
mechanisms into this same tasking implementation (semaphores,
queued "fair" access to scarce resources, etc), just as it
would be possible to add an element of randomness to the
dispatch logic of defer(), so that tasks would become truly
asynchronous.  I encourage anyone who feels like it, to
experiment with these things.  I'm simply delighted to have
been able to put such a powerful teaching and modelling tool
in your hands so easily and cheaply.